package newBee.class1;

/**
 * https://leetcode.cn/problems/remove-duplicate-letters/description/
 * 去除重复字母
 */
public class Code07_smallestSubsequence {
    public static void main(String[] args) {
        String str = "cbacdcbc";
        String ans = smallestSubsequence(str);
        System.out.println("ans = " + ans);
    }

    /**
     * cnts[t]：判断后面是否还有该字符
     */
    public static String smallestSubsequence(String str) {
        int r = 0, max = 26;
        int[] stack = new int[max];
        int[] cnts = new int[max]; // 字符词频表
        boolean[] enStack = new boolean[max]; // 字符入栈标识

        char[] chars = str.toCharArray();

        for (char c : chars) cnts[c - 'a']++; // 统计字符词频

        for (char c : chars) {
            // 词频表里是否存在
            if (!enStack[c - 'a']) {
                // 1.入栈大压小
                // 2.栈顶和c比较，大于栈顶，入栈
                // 3.栈顶的值在出栈前还需判断后面是否还有该字符，没有则不能出栈
                while (r > 0 && stack[r - 1] > c && cnts[stack[r - 1]  - 'a'] > 0) { // 栈顶字符词频 > 0
                    // 将新字符压栈，c的字符范围在： ? < c < r-1
                    // 将是否在站内标识位设为false,因为能进入 while循环，表示后面还育机会再次进栈
                    enStack[stack[r - 1] - 'a'] = false;
                    --r; // 出栈
                }
                // 当 c 已经找不到比自身大的元素时，说明此时栈顶就是小于c的，直接入栈
                stack[r++] = c;
                enStack[stack[r - 1]  - 'a'] = true; // 将 c 设置为true，以避免下一个c来的时候重复处理
            }
            // 每边里一个需要对字符数量进行--
            cnts[c - 'a']--;
        }
        return new String(stack, 0, r);
    }
}
